In the prior art, in a method known to be effective for a key word search from a great amount of character strings, a state transition diagram is prepared from a key word and each character making up a character string of a text to be searched is checked with the state transition diagram to implement a key word search. See A. Aho et al., "Efficient String Matching: An Aid to Bibliographic Search", Communications of the ACM, Vol. 18, No. 6, June 1975, pp. 33-340.
In the aforementioned prior art (hereinafter called then "FSA method"), assume, for example, that three key words are provided including "HEI RETSU" () (a phrase comprising two kanji characters meaning "parallel"), "KEI SAN KI" () (a phrase comprising three kanji characters meaning "computer") and "SEI GYO HOU HOU" () (a phrase comprising four kanji characters meaning "control method"). A transition diagram is prepared as shown in FIG. 12A which is stored in the form of the state transition table of FIG. 12B. Each character of the text is checked sequentially with this transition table for a search. In the example of FIG. 12A, if the character of the input text is "HEI" (), transition is made to state 1; if the character is "KEI" (), transition is made to state 3; and if the character is "SEI" (), transition is made to state 6. If the text character is "RETSU" in state 1, transition is made to state 2. Since state 2 is the final state, it is known that the key word "HEI RETSU"(), has been searched for. With regard to the other key word "KEI SAN KI" (), or "SEI GYO HOU HOU" (), it is known whether these key words have been searched for or not by determining whether transition is made to state 5 or 9 respectively. In this way, the FSA method is an efficient method capable of searching for a plurality of key words. The actual processing of searching a character string by the FSA method is realized by a program as shown in FIG. 12C. The FSA method, though superior as described above, has the problem of sequential processing. As shown in FIG. 12C, in the FSA method, after initialization (step 1203), whether the present state is the final one is checked (step 1205) at each time of application of one text character (step 1204), and if so, the position and the length of the text in which a key word has been found is produced (step 1206). And the state transition table is checked from the present state and the text characters thereby to determine the state to which the next transition is to be made (steps 1207 to 1211), so that the state and the text position are updated (step 1211). A similar processing is repeated for the next text characters.
Specifically, the state of the destination of transition is determined only at the end (step 1212) of the processing of each text character, and the processing of the next text character cannot be started until the determination of the state of the destination of transition. As a result, the processing becomes essentially sequential. In the case where an attempt is made to increase the search speed by use of a parallel processing technique such as the pipeline processing with an exclusive hardware, however, the above-mentioned sequential characteristic poses the problem of inapplicability of the search by the FSA method.
Accordingly, an object of the present invention is to provide a method and a system for character string search suitable for searching for a key word at high speed from a text character string in a great amount of character strings.
Another object of the present invention is to provide a new method and a system for character string search suitable for increasing the processing speed by parallel processing such as the pipeline processing.
Still another object of the present invention is to provide a method of character string search in which the character string search processing based on the FSA method is executable by vectorial processing with a vector computer.